/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tree;
import common.Dicionario;

/**
 *
 * @author leonardo
 */
public class AvlTree {
	
	private AvlNode root = null;
	private String caminho = "";
	
	/* Altura da árvore */
	private static int height ( AvlNode t ) {
		return t == null ? 0 : t.height;
	}
	
	/* Maior valor entre left right */
	private static int max ( int lhs, int rhs ) {
		return lhs > rhs ? lhs : rhs;
	}
	/* Fator de Balanceamento */
	private int getFactor (AvlNode t) {
		return height( t.left ) - height( t.right );
	}
	public AvlNode search (String el) {
	      return search(root,el);
	}
	private AvlNode search (AvlNode p, String el) {
		while (p != null) {
			if (el.equals(p.key.getPalavra())) return p;
			else if (el.compareTo(p.key.getPalavra()) < 0) p = p.left;
			else p = p.right;
		}
		return null;
	}

	private static AvlNode doRightRotation( AvlNode k2 ) {
		AvlNode k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;
		k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
		k1.height = max( height( k1.left ), k2.height ) + 1;
		return k1;
	}
	private static AvlNode doLeftRotation( AvlNode k1 ) {
		AvlNode k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;
		k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
		k2.height = max( height( k2.right ), k1.height ) + 1;
		return k2;
	}
	private static AvlNode doDoubleRightRotation( AvlNode k3 ) {
		k3.left = doLeftRotation( k3.left );
		return doRightRotation( k3 );
	}
	private static AvlNode doDoubleLeftRotation (AvlNode k1) {
		k1.right = doRightRotation( k1.right );
		return doLeftRotation( k1 );
	}
	private AvlNode insert (Dicionario x, AvlNode t) {
		if( t == null ) t = new AvlNode( x, null, null );
		else if( x.getPalavra().compareTo(t.key.getPalavra()) < 0 ) t.left = insert( x, t.left );
		else if( x.getPalavra().compareTo(t.key.getPalavra()) > 0 ) t.right = insert( x, t.right );
		if ( getFactor(t) == 2 ) {
			if (getFactor (t.left)>0) t = doRightRotation( t );
			else t = doDoubleRightRotation( t );
		}
		else if ( getFactor(t) == -2 ) {
			if ( getFactor(t.right)<0 ) t = doLeftRotation( t );
			else t = doDoubleLeftRotation( t );
		}
		t.height = max( height( t.left ), height( t.right ) ) + 1;
		return t;
	}
	public boolean insert (Dicionario x) {
		if (search(x.getPalavra()) != null) return false;
			root = insert (x, root);
			return true;
	}
	
	public void factor_inorder() {
		factor_inorder(root);
	}
	private void factor_inorder(AvlNode p) {
		if (p != null) {
			factor_inorder(p.left);
			System.out.print("Nó: " + p.key + " Fator: " + getFactor(p) + "\n");
			factor_inorder(p.right);
		}
	}
	public void percorre() {
		percorre(root);
	}

	private void percorre (AvlNode p) {
		if (p != null) {
			percorre(p.left);
			caminho += p.getKey().getPalavra();
			for(int i = 0; i < p.getKey().getDefinicoes().size(); i++) {
				caminho += "#" + p.getKey().getDefinicoes().get(i);
			}
			caminho += "\n";
			percorre(p.right);
		}
	}

	public String getCaminho() {
		percorre();
		return caminho;
	}
	
}